package com.yangzhe.algorithm.c025;


import java.io.*;

/**
 *  测试链接 : https://www.luogu.com.cn/problem/P1177
 */
public class HeapSort_Acm {

	private static int MAX_LENGTH = 100001;

	private static int n = 0;

	private static int[] nums = new int[MAX_LENGTH];

	public static void main(String[] args) throws IOException {
		try(InputStreamReader inputReader = new InputStreamReader(System.in);
			BufferedReader reader = new BufferedReader(inputReader);) {
			StreamTokenizer token = new StreamTokenizer(reader);
			token.nextToken();

			n = (int)token.nval;

			for (int i = 0; i < n; i++) {
				token.nextToken();
				nums[i] = (int)token.nval;
			}

		}

		heapSort2();

		try(OutputStreamWriter outputWriter = new OutputStreamWriter(System.out);
			PrintWriter writer = new PrintWriter(outputWriter);) {
			for (int i = 0; i < n; i++) {
				writer.print(nums[i] + " ");
			}
		}
	}

	/**
	 * 第一种排序：
	 * 1. 从顶到底建立大根堆 复杂度 O(n * logn)
	 * 2. 建堆后调整 复杂度 O(n * logn)
	 * 整体复杂度 O(n * logn)
	 */
	public static void heapSort1() {
		// 1. 从顶到底建立大根堆
		for (int i = 0; i < n; i++) {
			heapInsert(i);
		}

		int size = n;
		// 2. 依次弹出最大值，再次建立大根堆
		while(size > 0) {
			swap(0, --size);
			heapify(0, size);
		}
	}

	/**
	 * 第二种排序：
	 * 1. 从底到顶建立大根堆 复杂度 O(n)
	 * 2. 建堆后调整 复杂度 O(n * logn)
	 * 整体复杂度 O(n * logn)
	 */
	public static void heapSort2() {
		// 1. 从底到顶建立大根堆
		for (int i = n - 1; i >= 0; i--) {
			heapify(i, n);
		}

		int size = n;
		// 2. 依次弹出最大值，再次建立大根堆
		while(size > 0) {
			swap(0, --size);
			heapify(0, size);
		}
	}

	public static void heapInsert(int index) {
		// 父节点index = (index - 1) / 2;
		// 如果当前节点比父节点大，则和父节点交换，即向上调整
		while(nums[(index -1) / 2] < nums[index]) {
			swap((index -1) / 2, index);
			index = (index -1) / 2;
		}

	}

	public static void heapify(int index, int size) {
		// 左孩子index = 2index + 1;
		// 右孩子index = 2index + 2;
		// 当前节点比孩子节点小，则和孩子节点中大的那个交换，即向下调整
		while(2 * index + 1 < size) {
			int maxChildIndex = (2 * index + 2 < size) && nums[2 * index + 2] > nums[2 * index + 1] ? (2 * index + 2) : (2 * index + 1);
			if (nums[maxChildIndex] > nums[index]) {
				swap(maxChildIndex, index);
				index = maxChildIndex;
			} else {
				break;
			}
		}
	}


	public static void swap(int x, int y) {
		int temp = nums[x];
		nums[x] = nums[y];
		nums[y] = temp;
	}

}
